package leetcode.code;

import leetcode.helper.HelpDebug;

public class Solution421 {

	private class Node {
		Node[] num = new Node[2];
	}

	private Node root;

	private void add(int num) {
		Node node = root;
		for (int i = 30; i >= 0; i--) {
			int first = (num >> i) & 1;
			if (node.num[first] == null) {
				node.num[first] = new Node();
			}
			node = node.num[first];
		}
	}

	private int search(int num) {// 找二进制位最接近num的那个已存在的数
		Node node = root;
		int ans = 0;
		for (int i = 30; i >= 0; i--) {
			int first = (num >> i) & 1;
			int find = first == 0 ? 1 : 0;
			if (node.num[find] != null) {
				node = node.num[find];
				ans |= (1 << i);
			} else {
				node = node.num[first];
			}
		}
		return ans;
	}

	public int findMaximumXOR(int[] nums) {
		root = new Node();
		for (int num : nums) {
			this.add(num);
		}
		int ans = 0;
		for (int num : nums) {
			ans = Math.max(ans, search(num));
		}
		return ans;
	}

	public static void main(String[] args) {
		String str = "[3,10,5,25,2,8]";// [3,10,5,25,2,8]
		Solution421 so = new Solution421();
		int ans = so.findMaximumXOR(HelpDebug.str2array3(str));
		System.out.println(ans);
//		System.out.println(Integer.toBinaryString(25));
	}

//	private int bu(int num) {
//	int ans = 0;
//	int pos = 0;
//	while (num > 0) {
//		int last = num & 1;
//		if (last == 0) {
//			ans = (1 << pos) | ans;
//		}
//		pos++;
//		num >>>= 1;
//	}
//	return ans;
//}
}
